package strings;

/**
 * @author pengfei.hpf
 * @date 2020/3/29
 * @verdion 1.0.0
 * 161. 相隔为 1 的编辑距离
 * 给定两个字符串 s 和 t，判断他们的编辑距离是否为 1。
 *
 * 注意：
 *
 * 满足编辑距离等于 1 有三种可能的情形：
 *
 * 往 s 中插入一个字符得到 t
 * 从 s 中删除一个字符得到 t
 * 在 s 中替换一个字符得到 t
 * 示例 1：
 *
 * 输入: s = "ab", t = "acb"
 * 输出: true
 * 解释: 可以将 'c' 插入字符串 s 来得到 t。
 * 示例 2:
 *
 * 输入: s = "cab", t = "ad"
 * 输出: false
 * 解释: 无法通过 1 步操作使 s 变为 t。
 * 示例 3:
 *
 * 输入: s = "1203", t = "1213"
 * 输出: true
 * 解释: 可以将字符串 s 中的 '0' 替换为 '1' 来得到 t。
 */
public class IsOneEditDistance {
    public boolean isOneEditDistance(String s, String t) {
        if(s == null || t == null){
            return false;
        }
        if(s.equals(t)){
            return false;
        }
        int slen = s.length();
        int tlen = t.length();
        if(Math.abs(slen - tlen) > 1){
            return false;
        }
        int edit = 0; //1: add 2: delete 0 modify
        int editCount = 0;
        if(slen < tlen){
            edit = 1;
        } else if(slen > tlen){
            edit = 2;
        }
        int i = 0;
        int j = 0;
        while(i < slen){
            char c1 = s.charAt(i);
            //TODO: 注意补位, 空字符串"" 与"a"
            char c2 = j < tlen ? t.charAt(j) : (char)0;
            if(c1 != c2){
                switch(edit){
                    case 1:
                        i--;
                        break;
                    case 2:
                        j--;
                        break;
                }
                editCount ++;
                if(editCount > 1){
                    return false;
                }
            }
            j ++;
            i ++;
        }
        return true;
    }

    //TODO: 官方题解!! 遇到不同剩下的就用equals 和substring去比较就好了!!! 自己不用再去比较!!!!
    public boolean isOneEditDistanceII(String s, String t) {
        int ns = s.length();
        int nt = t.length();

        // Ensure that s is shorter than t.
        if (ns > nt)
            return isOneEditDistanceII(t, s);

        // The strings are NOT one edit away distance
        // if the length diff is more than 1.
        if (nt - ns > 1)
            return false;

        for (int i = 0; i < ns; i++)
            if (s.charAt(i) != t.charAt(i))
                // if strings have the same length
                if (ns == nt)
                    return s.substring(i + 1).equals(t.substring(i + 1));
                    // if strings have different lengths
                else
                    return s.substring(i).equals(t.substring(i + 1));

        // If there is no diffs on ns distance
        // the strings are one edit away only if
        // t has one more character.
        return (ns + 1 == nt);
    }

}
